#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T --) {
    int n;
    cin >> n;
    string str;
    cin >> str;
    debug(str);
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i ++) {
      int u, v;
      cin >> u >> v;
      u --, v --;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    string s = " ";
    auto dfs = [&](auto &&dfs, int u, int fa) -> void {
      s += str[u];
      for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(dfs, v, u);
        s += str[u];
      }
    };
    dfs(dfs, 0, -1);
    n = s.size() - 1;
    vector<vector<int>> dp(n + 2, vector<int>(n + 1));
    for (int l = n; l >= 1; l --) {
      for (int r = l; r <= n; r ++) {
        dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
        if (s[l] == s[r]) {
          dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 2);
        }
      }
    }
    cout << dp[1][n] / 2 << endl;
  }
}